package com.gxc.string;

import java.util.LinkedList;

/**
 * 给定一个字符串 str，再给定 str 的最长回文子序列字符串 strlps, 请返回在添加字符最少的情况下，
 * 让 str 整体都是回文字符串的一种结果。
 * 进阶问题比原问题多了一个参数，请做到时间复杂度比原问题的实现低。
 * 输入
 * A1B21C
 * 121
 *
 * 输出
 * AC1B2B1CA
 *
 * 解法：
 * 一：
 * 根据最长回文子序列 确定最长回文子序列中心字符位置 i，
 * 字符串从 i 出发，同时往左右两边遍历，
 * 当str[i-k]==strlps[i-1]  str[i+j]=strlps[i+1]
 * 把i-k...i-1,i,i+1,. i+j 字符变为回文字符串，
 * 由于 i-k...i-1, i+1...i+j  肯定没有重复字符（如果有，则最长回文子序列会更长）
 */
public class AddPalindrome2 {

    public static void main(String[] args) {
        String str = "A1B21C";
        String strlps = "121";

        System.out.println(process2(str, strlps));
    }

    public static String process(String str, String strlps) {
        if (str == null || str.length()<2) return str;

        int mid = 0;
        if (strlps.length()%2 == 0) {
            mid = strlps.length()/2 - 1;
        } else {
            mid = strlps.length()/2;
        }
        LinkedList<Character> queue = new LinkedList<>();
        char[] chars = strlps.toCharArray();
        for (int i = 0; i <= mid; i++) {
            queue.add(chars[i]);
        }

        char[] charsStr = str.toCharArray();
        int strmid = 0;
        for (; strmid < charsStr.length; strmid++) {
            if (queue.peek() == charsStr[strmid]) {
                queue.poll();
            }
            //如果队列为空，则当前是 最长回文子序列中心字符位置
            if (queue.isEmpty()) break;
        }
        //最长回文子序列字符串是偶数
        if (strlps.length()%2 == 0) {

        }

        return "";
    }

    /**
     * 遍历
     * @param str
     * @param strlps
     * @return
     */
    public static String process2(String str, String strlps) {
        if (str == null || str.length()<2) return str;
        int strl = str.length();
        int strlpsl = strlps.length();
        //两倍的字符长度-回文长度就是 目标字符串的长度
        char[] res = new char[2 * strl - strlpsl];
        char[] strChars = str.toCharArray();
        char[] strlpsChars = strlps.toCharArray();

        int ls = 0;
        int le = strl - 1;
        int ss = 0;
        int se = strlpsl - 1;
        int rs = 0;
        int re = res.length-1;

        while (rs<=re) {
            while (strChars[ls]!=strlpsChars[ss]) {
                res[rs++] = strChars[ls];
                res[re--] = strChars[ls++];
            }
            while (ls<=le && strChars[le]!=strlpsChars[se]) {
                res[rs++] = strChars[le];
                res[re--] = strChars[le--];
            }
            if (rs<=re) {
                res[rs++] = strChars[ls++];
                res[re--] = strChars[le--];
            }
        }
        return String.valueOf(res);
    }

}
